package leetcode101.search_problem.bfs;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Synhard
 * @version 1.0
 * @Class leetcode101.graph.Code1
 * @Description 934. Shortest Bridge
 * In a given 2D binary array A, there are two islands.
 * (An island is a 4-directionally connected group of 1s not connected to any other 1s.)
 *
 * Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.
 *
 * Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)
 *
 * Example 1:
 *
 * Input: A = [[0,1],[1,0]]
 * Output: 1
 * Example 2:
 *
 * Input: A = [[0,1,0],[0,0,0],[0,0,1]]
 * Output: 2
 * Example 3:
 *
 * Input: A = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
 * Output: 1
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-04-05 9:02
 */
public class Code1 {

    public static void main(String[] args) {
        int[][] matrix = new int[][]{
                {0,0,0,1,1,0,0},
                {0,0,0,1,0,0,0},
                {0,0,0,1,0,0,0},
                {0,0,0,0,0,0,0},
                {0,0,0,0,0,0,0},
                {0,1,0,0,0,0,0},
                {0,1,1,0,0,0,0}
        };
        System.out.println(shortestBridge(matrix));
    }


    public static int[] directions = new int[]{-1, 0, 1, 0, -1};

    public static int shortestBridge(int[][] A) {
        int m = A.length, n = A[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int res = 0;
        boolean[][] check = new boolean[m][n];
        // dfs寻找第一个岛屿，并把第一个岛屿全部赋值为2
        outer: for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (A[i][j] == 1) {
                    dfs(A, queue, check, i, j);
                    break outer;
                }
            }
        }

        // 对已经找到的第一块岛屿进行BFS，求出组成岛屿的每一块小陆地距离另一块岛屿的距离
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] head = queue.poll();
                for (int j = 0; j < directions.length - 1; j++) {
                    assert head != null;
                    int nx = head[0] + directions[j];
                    int ny = head[1] + directions[j + 1];
                    /*
                    这里的意思是如果越界了,或者说已经访问过陆地了那么就停止这个方向上的搜索
                    去下一个方向尝试,这里的check[nx][ny]为true的岛屿可能是第一块陆地,也可能是为0的陆地
                     */
                    if (nx < 0 || nx > m - 1 || ny < 0 || ny > n - 1 || check[nx][ny]) {
                        continue;
                    }
                    /*
                    这里为什么能保证res就是最小值呢,因为每一层while循环操作的岛屿是每一块岛屿的第i步能够访问到岛屿的位置
                    所以这里一旦访问到1立马返回,返回的就是到第二块岛屿的最小步数.
                     */
                    if (A[nx][ny] == 1) {
                        return res;
                    }
                    queue.offer(new int[]{nx, ny});
                    check[nx][ny] = true;
                }
            }
            res++;
        }
        return -1;
    }

    /*
    找寻第一块陆地,并将其标成2
     */
    public static void dfs(int[][] A, Queue<int[]> queue, boolean[][] check, int i, int j) {
        if (i < 0 || i > A.length - 1 || j < 0 || j > A[i].length - 1 || A[i][j] == 0 || A[i][j] == 2) {
            return;
        }
        A[i][j] = 2;
        queue.offer(new int[]{i, j});
        check[i][j] = true;
        for (int k = 0; k < directions.length - 1; k++) {
            dfs(A, queue, check, i + directions[k], j + directions[k + 1]);
        }
    }
}

/*
解题思路就是首先暴力搜索第一个是1的岛屿,然后通过dfs进行遍历得到第一块大陆地,然后将第一块陆地标成2
然后对标成2的陆地使用bfs去搜索,看看谁第一个到另一块陆地.
 */
